package org.basis.algorithm.promote;

import java.util.LinkedList;

/**
 * 单调队列练习
 *
 * @author Mr_wenpan@163.com 2022/02/18 10:04
 */
public class SlidingWindowMaxArray01 {

    public static void main(String[] args) {

    }

    /**
     * 获取窗口内的最大值（使用单调队列求解）
     */
    public static int[] getMaxWindow(int[] arr, int w) {
        int index = 0;
        int[] res = new int[arr.length - w + 1];
        // 一个单调递减的队列
        LinkedList<Integer> queue = new LinkedList<>();

        for (int i = 0; i < arr.length; i++) {
            // 添加i位置前，先检查并维护队列中的单调性
            while (!queue.isEmpty() && arr[queue.peekLast()] <= arr[i]) {
                queue.pollLast();
            }
            queue.addLast(i);

            // 窗口向右滑动时，左边界需要失效一个位置，如果失效的位置正好是队列头部记录的位置，那么将队列头部的元素移除
            // 以i - w来表示窗口的左边界，这一步应该要保证在达到窗口长度之前
            if (queue.peekFirst() == i - w) {
                queue.removeFirst();
            }

            // 是否达到了窗口长度
            if (i >= w - 1) {
                // 此时窗口内部的最大值就是队列头部位置的数
                res[index++] = arr[queue.pollFirst()];
            }
        }

        return res;
    }

    /**
     * 暴力解法
     */
    public static int[] getMaxWindow2(int[] arr, int w) {
        if (arr.length < w) {
            throw new RuntimeException("没有最大值,数据不合规");
        }
        int index = 0;
        int[] res = new int[arr.length - w + 1];

        for (int i = 0; i <= arr.length - w; i++) {
            int max = arr[i];
            for (int j = i; j < i + w; j++) {
                max = Math.max(max, arr[j]);
            }
            res[index++] = max;
        }

        return res;
    }

}
